# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 20/50 最长递增子序列的个数
# leetcode第673题: https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
# Date: 2024/11/7
from typing import Callable

from leetcode import test


def findNumberOfLIS_dp(nums: list[int]) -> int:
    """使用动态规划来实现, 其中:
    dp[i]为以第i个数字为结尾的最长子序列的长度
    cnt[i]表示以第i个数字结尾的最长子序列的个数
    对于nums[i]来说, 最长的子序列就是在此前的最长升序子序列中添加一个nums[i].
    由于dp[j]表示了以nums[j]结尾的最长子序列的长度, 所以新的最长升序子序列如果要加上nums[i], 就必须满足nums[i] > nums[j].
    对于cnt[i]来说, 其等于满足所有dp[j] + 1 为 dp[i] 的cnt[j]的和.
    例如 nums = [1, 3, 5, 4, 7]
        dp  =  [1, 2, 3, 3, 4]
        cnt =  [1, 1, 1, 1, 2]
    """
    n, max_len, ans = len(nums), 0, 0
    dp, cnt = [0] * n, [0] * n

    for i, x in enumerate(nums):
        dp[i] = cnt[i] = 1
        for j in range(i):
            if x > nums[j]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]
                elif dp[j] + 1 == dp[i]:
                    cnt[i] += cnt[j]
        if dp[i] > max_len:
            max_len = dp[i]
            ans = cnt[i]  # 重置计数
        elif dp[i] == max_len:
            ans += cnt[i]

    return ans


def findNumberOfLIS_bis(nums: list[int]) -> int:
    """使用贪心 + 前缀和 + 二分查找
    没有搞明白
    其中d为一个二维数组, d[i]表示数组所有长度为i的最长升序子序列, 我们将nums[j]放置在d[i]的末尾, 这样d[i]中的元素就是有序的.
    定义cnt[i][j]为记录了以d[i][j]为结尾的最长升序子序列的个数的二维数组. cnt[i][j]的值通过检查d[i-1]和cnt[i-1]获得:
    将所有满足 d[i-1][k]<d[i][j] 的cnt[i-1][k]累加到cnt[i][j], 最后cnt[maxLen]的所有元素之和就是最终的答案
    """

    def bisect(n: int, f: Callable[[int], bool]) -> int:
        l, r = 0, n
        while l < r:
            mid = (l + r) // 2
            if f(mid):
                r = mid
            else:
                l = mid + 1
        return l

    d, cnt = [], []
    for v in nums:
        i = bisect(len(d), lambda i: d[i][-1] >= v)
        c = 1
        if i > 0:
            k = bisect(len(d[i - 1]), lambda k: d[i - 1][k] < v)
            c = cnt[i - 1][-1] - cnt[i - 1][k]
        if i == len(d):
            d.append([v])
            cnt.append([0, c])
        else:
            d[i].append(v)
            cnt[i].append(cnt[i][-1] + c)
    return cnt[-1][-1]


if __name__ == '__main__':
    n1 = [1, 3, 5, 4, 7]  # [1, 3, 4, 7] 和[1, 3, 5, 7]
    n2 = [2, 2, 2, 2, 2]  # 5
    n3 = [1, 2, 4, 3, 5, 4, 7, 2]  # [1,2,4,5,7] [1,2,3,5,7] [1,2,3,4,7]
    n4 = [1, 2, 1, 2, 1, 2]  # 6
    inp = [{"nums": n1}, {"nums": n2}, {"nums": n3}, {"nums": n4}, ]
    out = [2, 5, 3, 6]
    test.test_function(findNumberOfLIS_dp, inp, out, times=10)
    test.test_function(findNumberOfLIS_bis, inp, out, times=10)
